#include <iostream>
#include <unordered_map>

using namespace std;

struct LinkedListNode {
    int key, value;
    LinkedListNode* prev;
    LinkedListNode* next;
    LinkedListNode() : key(0), value(0), prev(nullptr), next(nullptr) {}
    LinkedListNode(int key, int value) : key(key), value(value), prev(nullptr), next(nullptr) {}
};

/*
缓存可以理解为就是一个kv，所以肯定要有一个map保存键值对，此时get为o(1)复杂度
为了让put为o(1)复杂度，需要使用一个list保存最近访问key
*/
class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new LinkedListNode();
        tail = new LinkedListNode();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        // 如果key不存在，返回-1
        if (!cache.count(key)) {
            return -1;
        }

        // 如果key存在，移动到链表头部，然后返回该值
        LinkedListNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (!cache.count(key)) {
            LinkedListNode* node = new LinkedListNode(key, value);
            cache[key] = node;
            addToHead(node);

            ++size;
            if (size > capacity) {
                LinkedListNode* removed = removeTail();
                cache.erase(removed->key);
                --size;
                delete removed;
            }
        } else {
            // 如果存在，更新value，并移动到头部
            LinkedListNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void moveToHead(LinkedListNode* node) {
        removeNode(node);
        addToHead(node);
    }

    void addToHead(LinkedListNode* node) {
        // 技巧：先修改与链表无关的节点node
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(LinkedListNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    LinkedListNode* removeTail() {
        LinkedListNode* node = tail->prev;
        removeNode(node);
        return node;
    }

private:
    int capacity;
    int size;
    LinkedListNode* head;
    LinkedListNode* tail;  
    unordered_map<int, LinkedListNode*> cache;
};

int main() {
    LRUCache cache(2);

    cache.put(1, 0);
    cache.put(2, 2);
    cout << cache.get(1) << endl;
    cache.put(3, 3);
    cout << cache.get(2) << endl;
    cache.put(4, 4);
    cout << cache.get(1) << endl;
    cout << cache.get(3) << endl;
    cout << cache.get(4) << endl;

    return 0;
}